# search.py
# ---------
# Licensing Information: Please do not distribute or publish solutions to this
# project. You are free to use and extend these projects for educational
# purposes. The Pacman AI projects were developed at UC Berkeley, primarily by
# John DeNero (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# For more info, see http://inst.eecs.berkeley.edu/~cs188/sp09/pacman.html

"""
In search.py, you will implement generic search algorithms which are called
by Pacman agents (in searchAgents.py).
"""

import util

class SearchProblem:
  """
  This class outlines the structure of a search problem, but doesn't implement
  any of the methods (in object-oriented terminology: an abstract class).

  You do not need to change anything in this class, ever.
  """

  def getStartState(self):
     """
     Returns the start state for the search problem
     """
     util.raiseNotDefined()

  def isGoalState(self, state):
     """
       state: Search state

     Returns True if and only if the state is a valid goal state
     """
     util.raiseNotDefined()

  def getSuccessors(self, state):
     """
       state: Search state

     For a given state, this should return a list of triples,
     (successor, action, stepCost), where 'successor' is a
     successor to the current state, 'action' is the action
     required to get there, and 'stepCost' is the incremental
     cost of expanding to that successor
     """
     util.raiseNotDefined()

  def getCostOfActions(self, actions):
     """
      actions: A list of actions to take

     This method returns the total cost of a particular sequence of actions.  The sequence must
     be composed of legal moves
     """
     util.raiseNotDefined()


def tinyMazeSearch(problem):
  """
  Returns a sequence of moves that solves tinyMaze.  For any other
  maze, the sequence of moves will be incorrect, so only use this for tinyMaze
  """
  from game import Directions
  s = Directions.SOUTH
  w = Directions.WEST
  return  [s,s,w,s,w,w,s,w]

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first [p 85].

    Your search algorithm needs to return a list of actions that reaches
    the goal.  Make sure to implement a graph search algorithm [Fig. 3.7].

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:

    print "Start:", problem.getStartState()
    print "Is the start a goal?", problem.isGoalState(problem.getStartState())
    print "Start's successors:", problem.getSuccessors(problem.getStartState())
    """
    open_list = util.Stack()
    closed_list = []
    dictionary = dict()
    nchilds = 0
    start_state = problem.getStartState()
    if ( problem.isGoalState(start_state) ):
        return '' #do nothing#

    successors = problem.getSuccessors(start_state)
    for i in successors:
        nchilds=nchilds+1
        open_list.push([i,nchilds])
        dictionary[nchilds] = [i[1], 0]

    closed_list.append(start_state)
    dictionary[0] = ['start', 0]

    while True:
        if open_list.isEmpty():
            return ''
        parent = open_list.pop()
        children = problem.getSuccessors(parent[0][0])
        for i in children:
            #check if already in closed_list
            fnd = False
            for j in closed_list:
                if (j == i[0]):
                    fnd = True
                    break
            if(not fnd):
                nchilds = nchilds + 1
                open_list.push([i, nchilds])
                dictionary[nchilds] = [i[1], parent[1]]
                if ( problem.isGoalState(i[0]) ):
                    route = get_route(dictionary, nchilds)
                    return route
        closed_list.append(parent[0][0])

def get_route(dictionary, n):
    route = []
    ch = n
    while(True):
        parent = dictionary[ch]
        if (parent[0] == 'start'):
            return route
        route.insert(0,parent[0])
        ch = parent[1]


def breadthFirstSearch(problem):
    "Search the shallowest nodes in the search tree first. [p 81]"
    open_list = util.Queue()            #list of to be explored nodes
    closed_list = []                    #store explored states here
    linked_list = dict()                #dictionary used to traceback the commands
    unique_id = 0                       #unique id for the dictionary

    start_state = problem.getStartState()
    if ( problem.isGoalState(start_state) ):
        return '' #do nothing#

    #structure of the list: [state, hash_id, total_cost]
    open_list.push([start_state, unique_id, 0])
    closed_list.append(start_state) #save the already explored state
    linked_list[unique_id] = ['start', unique_id]    #add the parent to the list

    while True:
        #sanity check
        if open_list.isEmpty():
            return ''

        parent = open_list.pop()
        p_state, p_id, p_cost = parent[0], parent[1], parent[2]

        childrens = problem.getSuccessors(parent[0])
        for i in childrens:
            if closed_list.count(i[0]) == 0:
                c_state, c_cmd, c_cost = i[0], i[1], i[2]

                #generate new id by incrementing, TODO: duplicates after 2^32!
                unique_id = unique_id + 1
                t_cost = 0 #todo used for graph search but not implemented yet
                open_list.push([c_state, unique_id, t_cost])
                linked_list[unique_id] = [c_cmd, p_id]
                if ( problem.isGoalState(c_state) ):
                    return ( get_route(linked_list, unique_id) )
                closed_list.append(i[0])

def get_route(dictionary, n):
    route = []
    ch = n
    while(True):
        parent = dictionary[ch]
        if (parent[0] == 'start'):
            return route
        route.insert(0,parent[0])
        ch = parent[1]



def uniformCostSearch(problem):
    "Search the node of least total cost first. "
    open_list = util.PriorityQueue()    #list of to be explored nodes
    closed_list = []                    #store explored states here
    linked_list = dict()                #dictionary used to traceback the commands
    unique_id = 0                       #unique id for the dictionary

    start_state = problem.getStartState()
    if ( problem.isGoalState(start_state) ):
        return '' #do nothing#

    #structure of the list: [state, hash_id, total_cost]
    open_list.push([start_state, unique_id, 0], 0)
    closed_list.append(start_state) #save the already explored states in a list
    linked_list[unique_id] = ['start', unique_id]    #add the parent to the dictionary

    while True:
        #sanity check
        if open_list.isEmpty():
            return ''

        parent = open_list.pop()
        p_state, p_id, p_cost = parent[0], parent[1], parent[2]
        childrens = problem.getSuccessors(parent[0])
        for i in childrens:
            if closed_list.count(i[0]) == 0:
                c_state, c_cmd, c_cost = i[0], i[1], i[2]

                #generate new id by incrementing, TODO: duplicates after 2^32!
                unique_id = unique_id + 1

                t_cost = c_cost + p_cost
                open_list.push([c_state, unique_id, t_cost], t_cost)
                linked_list[unique_id] = [c_cmd, p_id]
                if ( problem.isGoalState(c_state) ):
                    return ( get_route(linked_list, unique_id) )
                closed_list.append(i[0])

#do not check below, local functions used only in this class
def find_in_list(s, t_list):
    fnd = False
    for i in t_list:
        if (i == s): #if found, return true
            fnd = True
            break

    return fnd  #return False

def get_route(linked_list, n):
    route = []
    id_ = n
    while(True):
        parent = linked_list[id_] #find the parent with the id
        if (parent[0] == 'start'):
            return route
        route.insert(0,parent[0]) #insert the command of the parent to a list
        id_ = parent[1] #update to point to the new parent for the next iter



def nullHeuristic(state, problem=None):
  """
  A heuristic function estimates the cost from the current state to the nearest
  goal in the provided SearchProblem.  This heuristic is trivial.
  """
  return 0

def aStarSearch(problem, heuristic=nullHeuristic):
    "Search the node that has the lowest combined cost and heuristic first."
    open_list = util.PriorityQueue()    #list of to be explored nodes
    closed_list = []                    #store explored states here
    linked_list = dict()                #dictionary used to traceback the commands
    unique_id = 0                       #unique id for the dictionary

    start_state = problem.getStartState()
    if ( problem.isGoalState(start_state) ):
        return '' #do nothing#

    #structure of the list: [state, hash_id, total_cost]
    open_list.push([start_state, unique_id, 0], 0)
    closed_list.append(start_state) #save the already explored state
    linked_list[unique_id] = ['start', unique_id]    #add the parent to the list

    while True:
        #sanity check
        if open_list.isEmpty():
            return ''

        parent = open_list.pop()
        p_state, p_id, p_cost = parent[0], parent[1], parent[2]

        childrens = problem.getSuccessors(parent[0])
        for i in childrens:
            if closed_list.count(i[0]) == 0:
                c_state, c_cmd, c_cost = i[0], i[1], i[2]
                h_value = heuristic(c_state, problem)

                #generate new id by incrementing, TODO: duplicates after 2^32!
                unique_id = unique_id + 1

                t_cost = p_cost + c_cost + h_value

                open_list.push([c_state, unique_id, t_cost], t_cost)
                linked_list[unique_id] = [c_cmd, p_id]
                if ( problem.isGoalState(c_state) ):
                    return ( get_route(linked_list, unique_id) )
                closed_list.append(i[0])

def get_route(linked_list, n):
    route = []
    id_ = n
    while(True):
        parent = linked_list[id_] #find the parent with the id
        if (parent[0] == 'start'):
            return route
        route.insert(0,parent[0]) #insert the command of the parent to a list
        id_ = parent[1] #update to point to the new parent for the next iter


# Abbreviations
bfs = breadthFirstSearch
dfs = depthFirstSearch
astar = aStarSearch
ucs = uniformCostSearch